package com.ryujung.dfs_backtracking;

import java.util.*;

class Solution491 {
    /**
     * 1334234
     * 思路：
     * 1.重复的元素是否要跳过？ 不一定，相邻且重复需要跳过
     * 2.如何去重，防止重复的组合再次进入结果集？ 舍弃相邻的相同元素、还有呢？
     * 3.
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        // TODO 尝试多次未通过，明天再完成，今天dfs做有点多，头皮发麻
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> que = new ArrayDeque<>();
        dfs(nums, 0, que, res);
        return res;
    }

    /**
     * nums: -100 ~ 100
     * nums.length: 1 ~ 15
     * <p>
     * 去重思路：
     * 在for循环中，nums中相同的值只遍历一遍，
     * 因为当遍历到重复元素时，前者返回的结果中已经包含了后者的所有可能，
     */
    private void dfs(int[] nums, int index, Deque<Integer> que, List<List<Integer>> res) {
        if (index == nums.length) return;

        // -100~100
        Set<Integer> hasUsedSet = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            boolean isValid = que.isEmpty() || que.getLast() <= nums[i];
            if (!hasUsedSet.contains(nums[i]) && isValid) {
                que.addLast(nums[i]);
                if (que.size() >= 2) {
                    res.add(new ArrayList<>(que));
                }
                dfs(nums, i + 1, que, res);
                hasUsedSet.add(nums[i]);
                que.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Solution491 ss = new Solution491();
        System.out.println(ss.findSubsequences(new int[]{4, 6, 7, 7}));
        System.out.println(ss.findSubsequences(new int[]{4, 4, 3, 2, 1, 2}));
    }
}